package cn.chencq.sort;

public class HeapSort {

	public static void main(String[] args) {
		int[] arr = { 7, 5, 2, 4, 8, 2, 1, 3 };

		sort(arr);
		print(arr);
	}

	public static void sort(int[] a) {

		for (int i = a.length - 1; i > 0; i--) {
			max_heapify(a, i);

			// 堆顶元素(第一个元素)与Kn交换
			int temp = a[0];
			a[0] = a[i];
			a[i] = temp;
		}
	}

	/***
	 *
	 * 将数组堆化 i = 第一个非叶子节点。 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
	 * 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
	 *
	 * @param a
	 * @param n
	 */
	public static void max_heapify(int[] a, int n) {
		int child;
		for (int i = (n - 1) / 2; i >= 0; i--) {
			// 左子节点位置
			child = 2 * i + 1;
			// 右子节点存在且大于左子节点，child变成右子节点
			if (child != n && a[child] < a[child + 1]) {
				child++;
			}
			// 交换父节点与左右子节点中的最大值
			if (a[i] < a[child]) {
				int temp = a[i];
				a[i] = a[child];
				a[child] = temp;
			}
		}
	}

	public static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}
